LeetCode 435、无重叠区间

一、题目描述

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。 

提示:

• 1 <= intervals.length <= 10^5
• intervals[i].length == 2
• -5 * 10^4 <= starti < endi <= 5 * 10^4

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// LeetCode 435、无重叠区间：https://leetcode.cn/problems/non-overlapping-intervals/
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {

        // 第一步，先将原数组进行一个排序的操作
        // 左端排序和右端排序均可，这里采取左端排序的方式
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        // 此时，第一个元素的位置在第一个数组的末端，即最右侧位置
        // 即末端位置
        int end = intervals[0][1];

        // 需要移除的数量
        int count = 0;

        // 开始遍历排序好后的那些区间元素
        // 这些元素按照开始端的大小进行了升序排序
        for (int i = 1; i < intervals.length; i++) {

            // 在遍历过程中，只要发现当前元素的左端位置在之前某个元素的内部
            // 1、说明发生了重叠
            if (intervals[i][0] < end) {
                // 此时必须要移除一个
                // 移除尾部更大的那个元素
                // 因为它更长，会占据更大的区间
                // end 更新
                end = Math.min(end, intervals[i][1]);

                // 移除了一个
                count++;

            // 2、如果没有重叠，就不需要移除
            } else {

                // 只需要更新尾部的位置即可
                end = intervals[i][1];
            }
        }

        // 返回结果
        return count;
    }
}

**2、**C++ 代码

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        std::sort(intervals.begin(), intervals.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
            return a[0] < b[0];
        });

        int end = intervals[0][1];
        int count = 0;

        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < end) {
                end = std::min(end, intervals[i][1]);
                count++;
            } else {
                end = intervals[i][1];
            }
        }

        return count;
    }
};

3、Python 代码

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])  # 左端排序

        end = intervals[0][1]  # 末端位置
        count = 0  # 需要移除的数量

        for i in range(1, len(intervals)):
            if intervals[i][0] < end:  # 发生重叠
                end = min(end, intervals[i][1])  # 更新末端位置
                count += 1  # 移除了一个
            else:  # 没有重叠
                end = intervals[i][1]  # 更新末端位置

        return count